/*
 * meituan.com Inc.
 * Copyright (c) 2010-2018 All Rights Reserved.
 */

import org.junit.Test;

import java.util.Arrays;
import java.util.Random;

/**
 * <p>
 * 归并排序
 * </p>
 * @author LvJing
 * @version $Id:MergeSort.java v1.0 2018/7/21 下午3:17 LvJing Exp $
 */
public class MergeSort {

    /*
    基本思想：将两个或两个以上的有序表合并成一个新的有序表，要求合并在的数组是有序的
    操作方法：先把数组的左边变成有序表，再把右边变成有序表，最后把两个表合并成一个整体的有序表，而在左边表变成有序表的方式，也是通过这样把左边
    表进行切分成两部分进行递归。
     */

    private void sort(int[] arr, int low, int high) {
        if (low < high) {
            int mid = (low + high) / 2;

            sort(arr, low, mid);// 左边部分变成有序
            sort(arr, mid + 1, high);// 右边部分变成有序
            merge(arr, low, mid, high);
        }
    }

    private void merge(int[] arr, int low, int mid, int high) {
        int[] tempArr = new int[high - low + 1];// 创建high到low之间范围大小的数组
        int left = low;// 左指针
        int right = mid + 1;// 右指针
        int pos = 0;

        // 先从小到大覆盖填充数组
        while (left <= mid && right <= high) {
            if (arr[left] < arr[right]) {
                tempArr[pos++] = arr[left++];
            } else {
                tempArr[pos++] = arr[right++];
            }
        }

        // 把左边数组剩余没有填充的元素填充到数组中
        while (left <= mid) {
            tempArr[pos++] = arr[left++];
        }

        // 把右边数组剩余没有填充的元素填充到数组中，注意这时肯定只有左边或者右边一边才会有剩余元素
        while (right <= high) {
            tempArr[pos++] = arr[right++];
        }

        // 把临时数组排序后的结果填充回原数组
        for (int i = 0; i < tempArr.length; i++) {
            arr[i + low] = tempArr[i];
        }
        System.out.println(Arrays.toString(arr));
    }

    public void mergeSort(int[] arr) {
        if (arr == null || arr.length == 0 || arr.length == 1) {
            return;
        }

        System.out.println(Arrays.toString(arr));
        sort(arr, 0, arr.length - 1);
    }

    @Test
    public void test() {
        int[] arr = new int[10];
        Random random = new Random();
        for (int i = 0; i < arr.length; i++) {
            arr[i] = random.nextInt(100);
        }
        mergeSort(arr);
    }
}
